Candale Silviu (silviu) Standard Template Library reprezintă un ansamblu de mecanisme scrise în C++ pentru gestionarea eficientă a unor colecții de date, împreună cu algoritmi eficienți care prelucrează aceste date. Este parte a Bibliotecii Standard C++, fiind astfel disponibilă în orice compilator care respectă standardul C++.
Introducere
STL are trei componente fundamentale: containerele, iteratorii și algoritmii, precum și o serie de componente suplimentare: containerele speciale, functorii, alocatorii.
Containerele
Containerele sunt obiecte care conțin date (de orice tip, putând fi la rândul containere). Alocarea memoriei pentru conținutul containerelor se face automat (de regulă dinamic), de către container.
Containerele sunt de două tipuri: containere secvențiale și containere asociative.
Containerele secvețiale gestionează un ansamblu de elemente dispuse strict liniar. Fiecare element al containerului are o poziție bine stabilită, care nu depinde de valoarea elementului. Avem următoarele contaniere secvențiale:
- vector – gestionează o secvență de elemente asemănătoare tablourilor standard C;
- deque (double-ended queue)- este o coadă cu operații rapide de adăugare și eliminare la ambele capete;
- list – gestionează o listă alocată dinamic, oferind operațiile de bază cu aceasta.
Timpul necesar pentru operațiile uzuale asupra containerelor secvențiale este redat mai jos:
| Operație | vector | deque | list |
|---|---|---|---|
| Accesarea primului element | constant | constant | constant |
| Accesarea ultimului element | constant | constant | constant |
| Accesarea unui element oarecare | constant | constant | liniar |
| Adăugare/ștergere la început | liniar | constant | constant |
| Adăugare/ștergere la sfârșit | constant | constant | constant |
| Adăugare/ștergere oarecare | liniar | liniar | constant |
Containerele asociative sunt structuri de date în care fiecare element are asociată o anumită cheie și are o anumită valoare. Ordinea elementelor în container depinde de cheie și se poate schimba în funcție de celelalte elemente. Aceste containere implementează eficient operațiile de adăugare de noi elemente, ștergere a elementelor în funcție de cheie, precum și căutarea elementelor după cheie.
Sunt două familii de containere asociative:
- set – în care cheia și valoarea elementelor sunt identice; containerele de acest tip sunt:
- set – memorează elemente distincte; elementele sunt menținute în ordine (strict) crescătoare;
- multiset – elementele pot fi egale și sunt menținute în ordine crescătoare;
- unordered_set – memorează elemente distincte; nu este garantată o anumită ordine a elementelor;
- unordered_multiset – elementele pot fi egale și nu este garantată o anumită ordine a elementelor
- map – cheile și valorile diferă; accesul la elemente se face prin intermediul cheii; containerele de acest tip sunt:
- map – cheile sunt distincte; elementele sunt menținute în ordine (strict) crescătoare a cheilor;
- multimap – cheile pot fi egale și sunt menținute în ordinea crescătoare a cheilor;
- unordered_map – cheile sunt distincte; nu este garantată o anumită ordine a elementelor;
- unordered_map – cheile pot fi egale și nu este garantată o anumită ordine a elementelor.
Timpii necesari pentru operațiile de adăugare, ștergere și acces sunt logaritmici pentru containerele asociative care menține elementele ordonate și constanți pentru containerele care nu mențin elementele în ordine.
Iteratorii
Iteratorii reprezintă o generalizare a conceputului de pointer. Ei oferă acces la elementele containerelor într-o manieră uniformă, pentru toate containere și pentru toți algoritmii STL.
Operațiile cu iteratorii sunt similare cu operațiile cu pointeri, putându-i dereferenția, incrementa/decrementa, compara, aduna cu întreg, etc. Unele operații sunt disponibile pentru toți iteratorii, altele doar pentru cei ai unor anumite tipuri de container.
Algoritmii
Algoritmii prelucrează colecții de elemente. Aceste colecții pot fi containere, părți ale unor containere sau slte structuri de date care permit lucrul cu pointeri (de exemplu tablouri standard C).
Algoritmii sunt folosiți sub formă de funcții, iar prelucrările pe care le fac sunt diverse: sortări, căutări, modificări, etc.
Containere speciale
Containerele speciale sunt:
- bitset – folosit pentru manipularea eficientă a șirurilor de biți
- containere adaptor – acoperă necesități speciale și sunt create pornind de la containere standard: containerele stack și queue permit gestionarea ușoară a unei stive, respectiv a unei cozi și sunt create pe baza containerului deque, iar containerul priority_queue gestionează o coadă de priorități (heap) și este creat pe baza clasei vector.
Functori și alocatori
Functorii sunt obiecte care se folosesc în maniera unui apel de funcție. Sunt folosite frecvent în cadrul algoritmilor.
Alocatorii sunt obiecte care gestionează alocarea memoriei pentru orice obiect și, în particular, pentru obiectele care fac parte dintr-un container.